{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# DP Tensor Experiment - v2\n",
    "\n",
    "### Purpose:\n",
    "to evaluate whether it's possible to build an automatic sensitivity calculation mechanism which could reliably produce sensitivity scores using only a forward pass through a dynamic graph. However, we want to extend the v1 experiment in several directions:\n",
    "\n",
    "- we want to be able to track the per-user sensitvity for each datapoint (meaning multiple sensitivity metrics per datapoint, one per input user)\n",
    "- we want to be able to have an accountant which keeps track of the epsilon budget for each user, letting us ask the question \"how much noise should i add to satisfy the most constraining privacy budget\"?\n",
    "\n",
    "### Conclusions:\n",
    "\n",
    "- looks like it can be done - but it requires a lot of sparse operations (could be tough to vectorize in an SMPC compatible way)\n",
    "- haven't implemented the accountant yet - will try in the next experiment. However, it seems that keeping things in the sensitivity space is a sortof accountant in and of itself.\n",
    "- BUG: unfortunately I used Counter() which sets every value to be 0 automatically if it hasn't been set. However, there are edge cases when this will cause incorrect behavior (When the true range as defined by others doesn't overlap wtih 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "import numpy as np\n",
    "class PrivateNumber():\n",
    "    \n",
    "    def __init__(self, value, max_val, min_val):\n",
    "        self.value = value\n",
    "        self.max_val = max_val\n",
    "        self.min_val = min_val\n",
    "        \n",
    "    def __add__(self, other):\n",
    "        \n",
    "        # add to a private number\n",
    "        \n",
    "        if(isinstance(other, PrivateNumber)):\n",
    "\n",
    "            entities = self.entities.union(other.entities)\n",
    "            \n",
    "            new_val = self.value + other.value\n",
    "\n",
    "            entities = set(self.max_val.keys()).union(set(other.max_val.keys()))\n",
    "\n",
    "            new_max_val = Counter()\n",
    "            new_min_val = Counter()            \n",
    "            for entity in entities:\n",
    "                new_max_val[entity] = self.max_val[entity] + other.max_val[entity]\n",
    "                new_min_val[entity] = self.min_val[entity] + other.min_val[entity]\n",
    "\n",
    "            return PrivateNumber(self.value + other.value,\n",
    "                                new_max_val,\n",
    "                                new_min_val)\n",
    "        \n",
    "        entities = self.entities\n",
    "        \n",
    "        # add to a public number\n",
    "        \n",
    "        new_max_val = Counter()\n",
    "        new_min_val = Counter()        \n",
    "        for entity in entities:\n",
    "            new_max_val[entity] = self.max_val[entity] + other\n",
    "            new_min_val[entity] = self.min_val[entity] + other\n",
    "        \n",
    "        return PrivateNumber(self.value + other,\n",
    "                                new_max_val,\n",
    "                                new_min_val)\n",
    "\n",
    "    def __sub__(self, other):\n",
    "        return self + (-other)\n",
    "    \n",
    "    def __mul__(self, other):\n",
    "        \n",
    "        if(isinstance(other, PrivateNumber)):\n",
    "        \n",
    "            entities = self.entities.union(other.entities)\n",
    "        \n",
    "            new_self_max_val = Counter()\n",
    "            new_self_min_val = Counter()            \n",
    "            for entity in entities:\n",
    "                \n",
    "                # the biggest positive number this entity could contribute is when\n",
    "                # it is multiplied by the largest value of the same sign from other\n",
    "                new_self_max_val[entity] = max(self.min_val[entity] * other.xmin, \n",
    "                                               self.max_val[entity] * other.xmax)\n",
    "                \n",
    "                # the smallest negative number this entity could contribute is when\n",
    "                # it is multiplied by the largest value of the opposite sign from other\n",
    "                new_self_min_val[entity] = min(self.min_val[entity] * other.xmax,\n",
    "                                               self.max_val[entity] * other.xmin)\n",
    "                \n",
    "            new_other_max_val = Counter()\n",
    "            new_other_min_val = Counter()            \n",
    "            for entity in entities:\n",
    "                \n",
    "                # the biggest positive number this entity could contribute is when\n",
    "                # it is multiplied by the largest value of the same sign from other\n",
    "                new_other_max_val[entity] = max(other.min_val[entity] * self.xmin, \n",
    "                                                other.max_val[entity] * self.xmax)\n",
    "                \n",
    "                # the smallest negative number this entity could contribute is when\n",
    "                # it is multiplied by the largest value of the opposite sign from other\n",
    "                new_other_min_val[entity] = min(other.min_val[entity] * self.xmax,\n",
    "                                                other.max_val[entity] * self.xmin)\n",
    "                \n",
    "            new_max_val = Counter()\n",
    "            new_min_val = Counter()\n",
    "            \n",
    "            for entity in entities:\n",
    "                new_max_val[entity] = max(new_self_max_val[entity], new_other_max_val[entity])\n",
    "                new_min_val[entity] = min(new_self_min_val[entity], new_other_min_val[entity])\n",
    "\n",
    "            return PrivateNumber(self.value * other.value,\n",
    "                                    new_max_val,\n",
    "                                    new_min_val)\n",
    "        \n",
    "        entities = self.entities\n",
    "        \n",
    "        new_max_val = Counter()\n",
    "        for entity in entities:\n",
    "            new_max_val[entity] = self.max_val[entity] * other\n",
    "\n",
    "        new_min_val = Counter()\n",
    "        for entity in entities:\n",
    "            new_min_val[entity] = self.min_val[entity] * other\n",
    "        \n",
    "        if(other > 0):\n",
    "            return PrivateNumber(self.value * other,\n",
    "                                    new_max_val,\n",
    "                                    new_min_val)\n",
    "        else:\n",
    "            return PrivateNumber(self.value * other,\n",
    "                                    new_min_val,                                 \n",
    "                                    new_max_val)\n",
    "    \n",
    "    def __truediv__(self, other):\n",
    "        \n",
    "        if(isinstance(other, PrivateNumber)):\n",
    "            raise Exception(\"probably best not to do this - it's gonna be inf a lot\")\n",
    "            \n",
    "        entities = self.entities\n",
    "        \n",
    "        new_max_val = Counter()\n",
    "        for entity in entities:\n",
    "            new_max_val[entity] = self.max_val[entity] / other\n",
    "\n",
    "        new_min_val = Counter()\n",
    "        for entity in entities:\n",
    "            new_min_val[entity] = self.min_val[entity] / other\n",
    "        \n",
    "        return PrivateNumber(self.value / other,\n",
    "                                new_max_val,\n",
    "                                new_min_val)\n",
    "\n",
    "    def __gt__(self, other):\n",
    "        \"\"\"BUG!: Counter() defaults to 0\"\"\"\n",
    "        if(isinstance(other, PrivateNumber)):\n",
    "        \n",
    "            entities = self.entities.union(other.entities)\n",
    "        \n",
    "            new_self_max_val = Counter()\n",
    "            new_self_min_val = Counter()            \n",
    "            for entity in entities:\n",
    "                \n",
    "                if not (self.min_val[entity] > other.xmax or self.max_val[entity] < other.xmin):\n",
    "                    new_self_max_val[entity] = 1\n",
    "                else:\n",
    "                    new_self_max_val[entity] = 0\n",
    "                \n",
    "                new_self_min_val[entity] = 0\n",
    "                \n",
    "            new_other_max_val = Counter()\n",
    "            new_other_min_val = Counter()            \n",
    "            for entity in entities:\n",
    "                \n",
    "                if not (other.min_val[entity] > self.xmax or other.max_val[entity] < self.xmin):\n",
    "                    new_other_max_val[entity] = 1\n",
    "                else:\n",
    "                    new_other_max_val[entity] = 0\n",
    "                    \n",
    "                new_other_min_val[entity] = 0\n",
    "                \n",
    "            new_max_val = Counter()\n",
    "            new_min_val = Counter()\n",
    "            \n",
    "            for entity in entities:\n",
    "                new_max_val[entity] = max(new_self_max_val[entity], new_other_max_val[entity])\n",
    "                new_min_val[entity] = min(new_self_min_val[entity], new_other_min_val[entity])\n",
    "\n",
    "            return PrivateNumber(int(self.value > other.value),\n",
    "                                    new_max_val,\n",
    "                                    new_min_val)\n",
    "        \n",
    "        entities = self.entities\n",
    "        \n",
    "        new_max_val = Counter()\n",
    "        new_min_val = Counter()\n",
    "        for entity in entities:\n",
    "            \n",
    "            new_min_val[entity] = 0\n",
    "            \n",
    "            if(other <= self.max_val[entity] and other >= self.min_val[entity]):    \n",
    "                new_max_val[entity] = 1\n",
    "            else:\n",
    "                new_max_val[entity] = 0\n",
    "\n",
    "        return PrivateNumber(int(self.value > other),\n",
    "                                new_max_val,\n",
    "                                new_min_val)\n",
    "    \n",
    "\n",
    "    def __lt__(self, other):\n",
    "        \"\"\"BUG!: Counter() defaults to 0\"\"\"\n",
    "        if(isinstance(other, PrivateNumber)):\n",
    "        \n",
    "            entities = self.entities.union(other.entities)\n",
    "        \n",
    "            new_self_max_val = Counter()\n",
    "            new_self_min_val = Counter()            \n",
    "            for entity in entities:\n",
    "                \n",
    "                if not (self.min_val[entity] > other.xmax or self.max_val[entity] < other.xmin):\n",
    "                    new_self_max_val[entity] = 1\n",
    "                else:\n",
    "                    new_self_max_val[entity] = 0\n",
    "                \n",
    "                new_self_min_val[entity] = 0\n",
    "                \n",
    "            new_other_max_val = Counter()\n",
    "            new_other_min_val = Counter()            \n",
    "            for entity in entities:\n",
    "                \n",
    "                if not (other.min_val[entity] > self.xmax or other.max_val[entity] < self.xmin):\n",
    "                    new_other_max_val[entity] = 1\n",
    "                else:\n",
    "                    new_other_max_val[entity] = 0\n",
    "                    \n",
    "                new_other_min_val[entity] = 0\n",
    "                \n",
    "            new_max_val = Counter()\n",
    "            new_min_val = Counter()\n",
    "            \n",
    "            for entity in entities:\n",
    "                new_max_val[entity] = max(new_self_max_val[entity], new_other_max_val[entity])\n",
    "                new_min_val[entity] = min(new_self_min_val[entity], new_other_min_val[entity])\n",
    "\n",
    "            return PrivateNumber(int(self.value < other.value),\n",
    "                                    new_max_val,\n",
    "                                    new_min_val)\n",
    "        \n",
    "        entities = self.entities\n",
    "        \n",
    "        new_max_val = Counter()\n",
    "        new_min_val = Counter()\n",
    "        for entity in entities:\n",
    "            \n",
    "            new_min_val[entity] = 0\n",
    "            \n",
    "            if(other <= self.max_val[entity] and other >= self.min_val[entity]):    \n",
    "                new_max_val[entity] = 1\n",
    "            else:\n",
    "                new_max_val[entity] = 0\n",
    "\n",
    "        return PrivateNumber(int(self.value < other),\n",
    "                                new_max_val,\n",
    "                                new_min_val)\n",
    "    \n",
    "    def __neg__(self):\n",
    "        return self * -1\n",
    "    \n",
    "    def max(self, other):\n",
    "        \n",
    "        if(isinstance(other, PrivateNumber)):\n",
    "            raise Exception(\"Not implemented yet\")\n",
    "        \n",
    "        entities = self.entities\n",
    "        \n",
    "        new_min_val = Counter()\n",
    "        for entity in entities:\n",
    "            new_min_val[entity] = max(self.min_val[entity], other)\n",
    "            \n",
    "        return PrivateNumber(max(self.value, other),\n",
    "                                self.max_val,\n",
    "                                new_min_val)\n",
    "    \n",
    "    def min(self, other):\n",
    "        \n",
    "        if(isinstance(other, PrivateNumber)):\n",
    "            raise Exception(\"Not implemented yet\")\n",
    "        \n",
    "        entities = self.entities\n",
    "        \n",
    "        new_max_val = Counter()\n",
    "        for entity in entities:\n",
    "            new_max_val[entity] = min(self.max_val[entity], other)\n",
    "                \n",
    "        return PrivateNumber(min(self.value, other),\n",
    "                                new_max_val,\n",
    "                                self.min_val)\n",
    "    \n",
    "    def hard_sigmoid(self):\n",
    "        return self.min(1).max(0)\n",
    "    \n",
    "    def hard_sigmoid_deriv(self):\n",
    "        return ((self < 1) * (self > 0)) + (self < 0) * 0.01 - (self > 1) * 0.01\n",
    "        \n",
    "    def __repr__(self):\n",
    "        return str(self.value) + \" \" + str(self.max_val) + \" \" + str(self.min_val)\n",
    "    \n",
    "    @property\n",
    "    def xmin(self):\n",
    "        return self.min_val.most_common(len(self.min_val))[-1][1]\n",
    "    \n",
    "    @property\n",
    "    def xmax(self):\n",
    "        return self.max_val.most_common(1)[0][1]\n",
    "    \n",
    "    @property\n",
    "    def entities(self):\n",
    "        return set(self.max_val.keys())\n",
    "    \n",
    "    @property\n",
    "    def sensitivity(self):\n",
    "        sens = Counter()\n",
    "        for entity, value in self.max_val.items():\n",
    "            sens[entity] = value - self.min_val[entity]\n",
    "        return sens.most_common()[0][1]\n",
    "    \n",
    "x = PrivateNumber(0.5,Counter({\"bob\":4, \"amos\":3}),Counter({\"bob\":3, \"amos\":2}))\n",
    "y = PrivateNumber(1,Counter({\"bob\":1}),Counter({\"bob\":-1}))\n",
    "z = PrivateNumber(-0.5,Counter({\"sue\":2}),Counter({\"sue\":-1}))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = x > y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.sensitivity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = x + y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = a * z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1.0 Counter({'sue': 8, 'bob': 8, 'amos': 6}) Counter({'amos': -3, 'sue': -6, 'bob': -6})"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# class PrivacyAccountant():\n",
    "    \n",
    "#     def __init__(self, default_budget = 0.1):\n",
    "        \n",
    "#         self.entity2epsilon = {}\n",
    "#         self.entity2id = {}\n",
    "#         self.default_budget = default_budget\n",
    "        \n",
    "#     def add_entity(self, entity_id, budget=None):\n",
    "#         \"\"\"Add another entity to the system to be tracked.\n",
    "        \n",
    "#         Args:\n",
    "#             entity_id: a string or other unique identifier of the entity\n",
    "#             budget: the epsilon level defining this user's privacy budget\n",
    "#         \"\"\"\n",
    "        \n",
    "#         if(budget is None):\n",
    "#             budget = self.default_budget\n",
    "        \n",
    "#         self.entity2id[entity_id] = len(self.entity2id)\n",
    "#         self.entity2epsilon[self.entity2id[entity_id]] = budget\n",
    "        \n",
    "        \n",
    "# accountant = PrivacyAccountant()\n",
    "\n",
    "# class DPTensor():\n",
    "    \n",
    "#     def __init__(self, data, entities, max_values=None, min_values=None):\n",
    "        \n",
    "#         assert data.shape == entities.shape#[0:-1]\n",
    "\n",
    "#         self.data = data\n",
    "#         self.entities = entities\n",
    "        \n",
    "#         if max_values is None:\n",
    "#             max_values = np.inf + np.zeros_like(self.data)\n",
    "            \n",
    "#         assert max_values.shape == data.shape\n",
    "#         self.max_values = max_values    \n",
    "        \n",
    "#         if min_values is None:\n",
    "#             min_values = -np.inf + np.zeros_like(self.data)            \n",
    "            \n",
    "#         assert min_values.shape == data.shape            \n",
    "#         self.min_values = min_values\n",
    "\n",
    "#     def sum(self, dim=0):\n",
    "        \n",
    "#         _new_data = self.data.sum(dim)\n",
    "        \n",
    "#         return _new_data\n",
    "    \n",
    "#     @property\n",
    "#     def sensitivity(self):\n",
    "#         return self.max_values - self.min_values\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [],
   "source": [
    "# results, tags = grid.search(\"diabetes\",\"#data\", verbose=False)\n",
    "# dataset = results['alice'][0][0:5][:,0:4]\n",
    "# n_ent = dataset.shape[0]\n",
    "# n_classes = dataset.shape[1]\n",
    "\n",
    "# for i in range(n_ent):\n",
    "#     accountant.add_entity(\"Diabetes Patient #\" + str(i))\n",
    "    \n",
    "# d2 = dataset.clone().get()\n",
    "# entities = th.arange(0,n_ent).view(-1,1).expand(n_ent,n_classes)#.unsqueeze(2)\n",
    "# db = DPTensor(data=d2, \n",
    "#               entities=entities, \n",
    "#               max_values=d2.max(0)[0].expand(n_ent,n_classes), \n",
    "#               min_values=d2.min(0)[0].expand(n_ent,n_classes))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
